5. Routing Fundamentals¶

This note introduces routing: what it is, why we need it, and challenges of routing.

Outline¶

• Setting the Scene

• Theoretical Perspective and Routing Validity

Setting the Scene¶

Disclaimer¶

There are an endless numbers of possible solutions to routing. We will constrain the initial discussion of how "archetypal Internet" works.

Recall Packets¶

Packets have a payload (actual data) and headers (metadata). The headers must contain destination address, which implies that a host has an address (or more than one). For now, we will think of hosts having one address.

What is a Router?¶

A router is an intermediate node that is usually connected to multiple neighbors.

Why do we have Routers? 1. If we were to put a link that goes from every router to other router, the Internet wouldn't scale. Consider adding an \(n\) router, we would need to connect \(n - 1\) new switches. However, this approach is very robust. But everyone gets a reserved link to send data to each other. 2. If all hosts share the same wire, it scales really well (adding a bit more wire). However, it is not robust; one wire breaks, hosts can disconnect completely from each other. Also, everyone is fighting for the same bandwidth. Very cheap.

These two approaches might combine into:

1. Way fewer links tha a full mesh!
2. But more than just a single link
3. Alternate paths!

Challenges of Routing¶

The basic challenge

• When a packket arrives at a router, how does the router know where to send it next such that it will eventually arive at the desried destination

We want to find paths which are good: Good may have several meanings (cheapest, fewest number of hops)

• No random routing: random routing is wasteful in terms of resources and time.

• No just sending it to everyone (it works, but it congests the network, super wasteful)

We want to adapt to arbitrary topologies

• The graph describing a network can vary a lot!

• Different networks (parts of the Internet) may use different routing, but generality is good

• Especially since every topology is dynamic (any router can go down)

Forwarding Problem¶

When a packet arrives, router forwards it to one of its neighbors. You want to make the decision about which neighbor quickly. This implies the decision process is simple. The solution: use a table

Given tables, decisions depends only on destination field of packet

• We call it destination-based forwarding/routing. Very common. One of those "archetypal Internet" things. We will think of alternatives later

Two Things Routers Do¶

1. Forwarding

2. Looks up packet's destination in table and sends packet to given neighbor

3. Inherently local: depends only on arriving packet and local table

4. Primary responsibility of router's data plane

5. Time scale: per packet arrival (nanoseconds?)

6. Routing

7. Communicates with other routers to deterine how to populate tables for forwarding

8. Inherently global: must know about all destinations, not just local ones

9. Primary responsibility of router's control plane

10. Time scale: per network event (e.g. per failure)

Theory¶

Directed Delivery Trees¶

We can graph paths packets to a destination will take if they follow tables.

NextHop becomes an arrow

• Only one NextHop per destination, which means only one outgoing arrow per node!. Once paths "meet", they never split

The set of all paths create "directed delivery tree"

• Must cover every node (we want to be able to reach it from anywhere)

It is an oriented spanning tree rooted at the destination

• Spanning tree: a tree that touches every node (no cycles)

Routing State Validity¶

Earlier, said we wanted "goog" paths between hosts. Notion of goodness is flexible, but minimum requirement must be that packets actaully reach their destinations.

It would be usefule to be able to reason about this. This is articulated by Scott Shenker as routing state validity.

• Local routing state is table in single router. By itself, the state in a single router can't be evaluated for validity. It must be evaluated in terms of the global context.

• Global state is collection of tables in all routers. Global state determines which paths packets take. It is valid if it produces forwarding decisions that always deliver packets to their destinations

Goal of routing protocols: compute valid state:

• Eventually talk about how you build routing state

But given some state ... how can you tell if it's valid? Need a succint correctness condition for routing... what makes routing correct/incorrect?

Global routing state is valid if and only if: - For each destination: there are no dead ends, there are no loops

Dead end: when there is no outgoing link (next-hop)

• Packet arrives, but is not forwarded (e.g., because there's no table entry for destination)

• The destination doesn't forward, butdoesn't count as a dead end!

• But other hosts generally are dead ends, since hosts don't generally forward packets

Loop: when packet cycles around the same set of nodes

• If forwarding is deterministic and only depends on destination field, this will go on indefinitely.

If there are no loops or dead ends, that is sufficient to know the state is valid (This is more subtle):

• Assume the routing state has no loops or dead ends

• Packet can't hit the same node twice (no loops)

• Packet can't stop before hitting destination (no dead ends)

• So a packet must keep wandering the network, hitting different nodes. Only a finite number of unique nodes to visit. Must eventually hit the destination

• Thus: if no loops and no dead ends, then routing state is valid.

Validation¶

Couple Notes¶

Hosts generally do not participate in routing. In common cases, hosts: 1. Have a single link to a single router 2. Have a default route that sends everything to that router

They are not interesting, so we often ignore them except as destinations

Routers might be legal destinations (in addition to hosts) - Depends on network design

• Internet Protocol routers can be

• But how often have you wanted to talk to a specific router?

• Host-to-host communication much more common: we'll often ignore routers as destinations

• But do think of all routers as potential sources (packets may arrive in unexpected ways)

Verifying Routing State Validity¶

Focus only on a single destination. Ignore all other hosts. Ignore all other routing states

1. For each router, mark outgoing edge with arrow (point at next hop). There can only be one at each node (destination-based)
2. Eliminate all links with no arrows
3. Look at what's left: state is valid if and only if remaining graph is a directed delivery tree (all paths point towards root)

There is a dead end in the second image.

There is a dead end in this example

Very easy to check validity of routing state for a particular destination.

1. Dead ends are obvious: a node with no outgoing arrow can't reach destination
2. Loops are obvious: disconnected from destination

Now just repeat for each destination

Note on Generality¶

We are looking at this from perspective of destination-based routing. Same basic no loops or dead ends conditions generalizes to at least* any other system that does deterministic forwarding based on fixed packet headers (that is, it is not limited to destination-based routing)

We just need to:

• Make one minor addition

• Carefully consider what constitutes a loop

Bellman-Ford Algorithm¶

Two things we know about networks... 1. They are distributed (many independent components) 2. They are asynchronous (components don't operate in sync)

Very promising algorithm to turn into a routing protocol:

my_number = infinity
offer_to_neighbors(my_number + 1)

while True:
    offer = wait_for_offer_from_a_neighbor()
    if offer < my_number:
        my_number = offer
        offer_to_neighbors(my_number + 1)

Distance-Vector Protocols¶

Routing protocols that work like this are called Distance-Vector protocols

• Adjacent routers conceptually exchange a vector (i.e., array) of distances. More like a vector of (destination, distance) tuples?

Used in ARPANET (Internet precursor) as far back as 1969

Later used by XEROX

Then by routed in Berkeley Software Distribution Unix 1983

• Routed's protocol standardized as RFC 1058 (Routing Information Protocol / RIP) in 1988

• Updated for classless addressing (we'll find out about that) in RFC 1723 in 1994

• Updated for IPv6 in RFC 2080 in 1997

• Kind of the "prototypical distance-vector protocol"

DV pretty widely deployed historically; less popular today, but not dead

Cisco EIGRP (1993) more advanced, published in RFC 7868 in 2016.

Babel published as experimental RFC 6126 in 2011; actively worked on